/**
 * @version: V1.0
 * @Title: CountSort.java
 * @Description:
 * @author wangshipeng
 * @date 2022-01-13 23:22
 * @Copyright: 2022-01-13
 */

package com.peng.sort;

import java.util.Arrays;

/**
 * @author wangshipeng
 * @ClassName: CountSort
 * @Description: 计数排序
 * @date 2022-01-13 23:22
 */
public class CountSort {

    public static void sort(int[] arr) {
        int max = Integer.MIN_VALUE;
        for (int val : arr) {
            max = Math.max(val, max);
        }
        int[] buckets = new int[max + 1];

        for (int val : arr) {
            buckets[val]++;
        }
        int j = 0;
        for (int i = 0; i < buckets.length; i++) {
            while (buckets[i]-- > 0) {
                arr[j++] = i;
            }
        }

    }

    public static void main(String[] args) {
        int[] arr = {1, 50, 30, 20, 60, 8, 9, 2, 3, 4, 5, 6, 7, 8, 10, 24};
        sort(arr);
        System.out.println(Arrays.toString(arr));
    }
}
